package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/16 15:44
 * @描述 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 */

public class Solution17 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("32"));
    }
        public static List<String> letterCombinations1(String digits) {
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) {
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }

        public static void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }


    static String[] lib=new String[]{"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public static List<String> letterCombinations(String digits){
        int len=digits.length();
        List<String>  ans = new ArrayList<>();
        if(len==0){
            return ans;
        }
        String first=lib[Integer.parseInt(String.valueOf(digits.charAt(0)))];
        for (int i = 0; i < first.length(); i++) {
            ans.add(String.valueOf(first.charAt(i)));
        }
        if(len==1){
            return ans;
        }
        System.out.println("first:  "+ans);
        for(int i=1;i<len;i++){
//            StringBuilder sb=new StringBuilder();
            int tag= Integer.parseInt(String.valueOf(digits.charAt(i)));
            expand(ans,tag);
            System.out.println("tag:   "+tag+"ans:   "+ans);
        }
        return ans;
    }

    public static void expand(List<String> list,int expand){
        List<String> basic=new ArrayList<>(list);
        int len=list.size();
        list.clear();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < lib[expand].length(); j++) {
                list.add(basic.get(i)+lib[expand].charAt(j));
            }
        }
    }



    static Map<Character, String> phoneMap1 = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};
    public static List<String> letterCombinations2(String digits){
        int len=digits.length();
        List<String>  ans = new ArrayList<>();
        if(len==0){
            return ans;
        }
        String first=phoneMap1.get(digits.charAt(0));
        for (int i = 0; i < first.length(); i++) {
            ans.add(String.valueOf(first.charAt(i)));
        }
        if(len==1){
            return ans;
        }
//        System.out.println("first:  "+ans);
        for(int i=1;i<len;i++){
//            StringBuilder sb=new StringBuilder();
            Character tag= digits.charAt(i);
            expand1(ans,tag);
//            System.out.println("tag:   "+tag+"ans:   "+ans);
        }
        return ans;
    }

    public static void expand1(List<String> list,Character expand){
        List<String> basic=new ArrayList<>(list);
        int len=list.size();
        list.clear();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < phoneMap1.get(expand).length(); j++) {
                list.add(basic.get(i)+phoneMap1.get(expand).charAt(j));
            }
        }
    }
}
